package sort;

import static net.ftng.commons.lang.utils.MathUtils.randomLong;
import static net.ftng.commons.lang.utils.PrintUtils.println;
import net.ftng.commons.lang.utils.ArrayUtils;

import org.junit.Test;

public class MergeSort {

    public static Long[] sort(final Long[] array) {

        int size = array.length;
        if (size < 2) {
            return array;
        }
        int maxIndex = size - 1;
        int subArray0Size = size / 2 - 1;
        Long[] subArray0 = ArrayUtils.subArray(array, 0, subArray0Size);
        Long[] subArray1 = ArrayUtils.subArray(array, subArray0Size + 1, maxIndex);
        Long[] sortedSubArray0 = sort(subArray0);
        Long[] sortedSubArray1 = sort(subArray1);
        Long[] mergedArray = merge(sortedSubArray0, sortedSubArray1);
        return mergedArray;
    }

    public static Long[] merge(final Long[] array0, final Long[] array1) {

        int length0 = array0.length;
        int length1 = array1.length;
        int size = length0 + length1;
        Long[] result = new Long[size];
        int index = 0;
        int index0 = 0;
        int index1 = 0;
        while (index < size) {
            if (index0 < length0) {
                Long element0 = array0[index0];
                if (index1 < length1) {
                    Long element1 = array1[index1];
                    if (element0 < element1) {
                        result[index] = element0;
                        index0++;
                    } else {
                        result[index] = element1;
                        index1++;
                    }
                } else {
                    result[index] = element0;
                    index0++;
                }
            } else {
                result[index] = array1[index1++];
            }
            index++;
        }
        return result;
    }

    @Test
    public void sort() {

        int size = 10;
        Long[] array = new Long[size];
        for (int i = 0; i < size; i++) {
            array[i] = randomLong(0, size);
        }
        println(array);
        Long[] sortedArray = MergeSort.sort(array);
        println(sortedArray);
    }
}
